package leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Created by baoyunfeng on 2019/8/18.
 */
public class TopologicalSort {

    public static void main(String args[]) {
        int n = 5;
        int[][] adjacencyList = new int[n][];
        adjacencyList[0] = new int[2];
        adjacencyList[1] = new int[2];
        adjacencyList[2] = new int[2];
        adjacencyList[3] = new int[1];
        adjacencyList[4] = new int[0];

        adjacencyList[0][0] = 1;
        adjacencyList[0][1] = 2;
        adjacencyList[1][0] = 2;
        adjacencyList[1][1] = 3;
        adjacencyList[2][0] = 3;
        adjacencyList[2][1] = 4;
        adjacencyList[3][0] = 4;


        for (int i = 0; i < adjacencyList.length; i++) {
            for (int j = 0; j < adjacencyList[i].length; j++) {
                System.out.print(adjacencyList[i][j] + " ");
            }
            System.out.println();
        }

        List<Integer> list = topologicalSort(n, adjacencyList);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    public static List<Integer> topologicalSort(int n, int[][] adjacencyList) {
        List<Integer> topoRes = new ArrayList();
        int inDegree[] = new int[n];
        for (int[] parent : adjacencyList) {
            for (int child : parent) {
                inDegree[child]++;
            }
            printNums(inDegree);
        }

        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                //队尾加入元素
                deque.offer(i);
                System.out.println(deque);
            }
        }

        while (!deque.isEmpty()) {
            int curr = deque.poll();
            topoRes.add(curr);
            for (int child : adjacencyList[curr]) {
                inDegree[child]--;
                printNums(inDegree);
                if (inDegree[child] == 0) {
                    deque.offer(child);
                    System.out.println("child:"+child+deque);
                }
            }
        }

        return n == topoRes.size() ? topoRes : new ArrayList<>();

    }

    private static void printNums(int nums[]) {
        for(int i = 0 ;i < nums.length;i++){
            System.out.print(nums[i]+" ");
        }
        System.out.println();
    }
}
